A denial-of-service (DoS) attack is a cyber-assault against a computer, server, network node, LAN or other networked entity that seeks to limit or prevent access to the Internet by overwhelming it with an unmanageable flood of requests (e.g. for a webpage or online resource) or emails (causing the email system to overload). A potentially more pernicious variant of this attack is a distributed denial-of-service (DDoS) attack, where the attacker infects a multitude of computers on the Internet (using for example a worm, virus or Trojan) and then directs this illicitly recruited army of computers to bombard the target with data packets.
A denial-of-service attack (“DoS attack”) against a IPv6 network node can exploit the IPv6 neighbor cache and its state machine by exhausting the cache's available resources. IPv6 is particular vulnerable because of the large number of potential entries in the neighbor cache and because the neighbor unreachability state machine is much more complex than the IPv4 ARP (Address Resolution Protocol).
FIG. 1 is a schematic depiction of the operation of a neighbor discovery finite state machine as used by an IPv6 node to resolve addresses for incoming packets.
As is known in the art, a common problem for Layer 3 (network) packet protocols is to translate a Layer 3 (L3) address into a Layer 2 (L2) address in order to send packets to neighboring nodes on a multiple-access network (e.g. an Ethernet LAN). For the sake of completeness, is recalled that seven layers are defined by the Open System Interconnection (OSI) model, namely Layer 1 (the physical layer), Layer 2 (the “media” layer or data link layer). Layer 3 (the network layer), Layer 4 (the transport layer), Layer 5 (the session layer), Layer 6 (the presentation layer), and Layer 7 (the application layer). The present invention is concerned with mapping between L3 and L2.
Just like IPv4, IPv6 uses a protocol and a cache to keep track of neighboring nodes' Layer 2 addresses. Whereas IPv4 uses the Address Resolution Protocol (ARP) and an ARP table for this purpose, IPv6 now implements a Neighbor Discovery Protocol (NDP) and a neighbor cache (NC) for this purpose. When NDP is used to resolve a neighbor's Layer 2 address, it performs “Neighbor Resolution”. But NDP is also used to perform Duplicate Address Detection (DAD), Router Discovery (RD), Neighbor Unreachability Detection (NUD), and (Stateless) Auto-configuration. NUD requires NDP to implement a Finite State Machine and a state is commonly stored in the neighbor cache.
Being a “cache”, the neighbor cache and ARP table are simply data structures that Maintain state about neighbors that are relevant at a particular point in time. Unnecessary data can be purged at any time and the resources held by the cache should be conserved as there may be a large number of neighbors.
The neighbor cache is maintained separately for each interface (although it is possible to have a plurality of neighbor caches for a given interface or to have a plurality of interfaces sharing one neighbor cache). IPv4 ARP tables are generally only applicable to broadcast media (e.g. Ethernets), but IPv6 NDP can be used on all media. In general, DAD should be performed, and NUD, RD, and auto-configuration may be useful too, even on non-multi-access networks.
The principles of operation of the Neighbor Discovery Finite State Machine (which are well known in the art) are illustrated in detail in FIG. 1 by way of background. In practice, as will be appreciated by those of ordinary skill in the art, some enhancements to the state machine shown in FIG. 1 might be necessary. For example, an entry can end up in STALE state forever if traffic is sent to a neighbor and then never again. Therefore, STALE entries should be cleaned out with a slow interval to conserve memory.
A denial-of-service attack against the neighbor cache (NC) of a network node (or end host or router) exploits a vulnerability in the NC in that the cache can fill up with potentially useless entries. This interrupts the target's connectivity with its neighbors. If the attack is successful in overwhelming the target, the consequences may have a ripple effect into the network at large, depending on the function that the targeted node was performing or the resources it was providing.
It should be noted that while the IPv6 standard does not require an implementation to use a neighbor cache internally per se, as long as the external behavior remains the same, the problem will still subsist since some type of state-full behavior is necessary to perform basic Neighbor Discovery functions.
In every software implementation, the amount of resources available for protocols is limited by the system's resources. Thus, each system has a fundamental limit to how many entries can be stored in a cache (mainly memory in this case) and the cache is always competing for resources with other parts of the system.
In every IP network, the theoretical limit to the cache can be determined by the size of the subnet. In IPv4, the size depends on the subnet mask. For example, a common IPv4/24 (class C) network has 256 possible addresses. In practice, the number of neighbors is smaller but one can easily see that an IPv4 ARP table is quite small. In comparison, a common IPv6 prefix is /64, which corresponds to 264 or 18,446,744,073,709,551,616 possible addresses per prefix assigned to an interface. A link-local prefix (fe80::/10 or longer) is always present (likely another 264). Therefore, whereas IPv4 ARP cache sizes are easy to handle and may even be pre-allocated, IPv6 neighbor caches should be managed more carefully. Complexity is further increased because of the IPv6 neighbor unreachability state machine. Therefore, IPv6 is particularly vulnerable to DoS attacks because the IPv6 neighbor cache has so many potentially valid entries and because the neighbor unreachability state machine complex, i.e. much more complex than the IPv4 ARP.
As is known in the art, the DoS attack may be local, where the attacker is attached to the same link as the target, or remote, where the attacker is multiple hops away from the target. Local attacks are easier to perform, have more impact and are harder to defend against. However, the local subnet is usually easier to control, meaning that an attacker must gain access to resources closer to the target, e.g. by gaining access to a building, or by breaking into a local node and controlling it remotely. Remote attacks are therefore more attractive to an attacker because of the complexities involved in gaining access to local nodes and the risk in getting caught. More importantly though, a local attacker has many more and simpler options when intending to disrupt the local network's operation than flooding the neighbor cache. While the present invention is directed primarily to defending against remote attacks, the methods described herein can also be used to blunt the impact of certain types of local attacks.
The simplest imaginable remote attack exploits the fact that the cache competes for resources with other parts of the target system. By sending a carefully crafted packet that has a destination under a prefix of the target's attached links, the attacker can make the target allocate a Neighbor Cache entry and try to solicit the destination's Layer 2 address on that link. If the destination address has been assigned to a node on the link (a real destination), it will answer, and if it does not (a bogus destination), there will be no answer. In both cases there will be an entry allocated in the NC for a period of time for that destination. If the attacker repeats the procedure for other destinations the cache fill will grow. Eventually the Neighbor Cache exhausts all memory on the target so that the target is unable to perform its intended function.
FIG. 2 schematically depicts a typical denial-of-service attack launched over the Internet 10 to which a plurality of legitimate users 12 are connected. A LAN (local area network) 14 is connected to the Internet via a router 16 (with or without a firewall) to enable the legitimate users 12 to communicate with one or more real neighbors 18 connected to the LAN 14. In a denial-of-service attack, a remote attacker 20 connects to the Internet 10 and launches a flood of packets at the router 16. As will explained below, the packets either contain real destination addresses that correspond to one of the real neighbors 18 on the LAN, or alternatively they are non-existent addresses, i.e. “bogus neighbors” 22.
FIG. 2 shows how a remote attacker can fill up the neighbor cache of a router by sending packets to bogus destinations on the router's attached networks. It also shows a variation of the attack where the target instead is a host. In this case packets will be sent to the host with a source address which indicates that the packet came from a direct neighbor.
Further analysis of the Neighbor Discovery State Machine shows that when real destinations are used by the attacker, then the entries will start out as INCOMPLETE, then become REACHABLE once the real neighbor answers, whereas bogus destinations will just be INCOMPLETE for a while and then time out and be deleted. The default time-out for the INCOMPLETE state is one second times three retransmits.
The foregoing means that, for example, if the attackers send minimally sized IPv6 packets (40 Bytes, just the IPv6 header plus 14B Ethernet header and 4B trailer) to random destinations on a 100 Mbps Ethernet link, it can, in theory, build up and sustain perhaps 645,000 bogus entries in the target's Neighbor Cache. In addition to that, an entry is logged for each of the real destinations it sends to.
The Neighbor Discovery standard prescribes that nodes must retain a small packet queue (of at least one packet) for each neighbor entry awaiting neighbor resolution. Given that each entry contains at least one IPv6 packet, one IPv6 address, one MAC address, and a state, this puts memory usage up in the range of 40MB in this example.
Of course, this simple calculation assumes that all traffic out one interface is generated by the attacker, which will not be the case in practice. But this illustrates the scale of the problems an attacker can cause on one interface. An attack on many interfaces that is paired with distributed attackers will be manifold worse.
As will be appreciated, the effect of a denial-of-service attack depends on the target system implementation and could, in some cases, prevent the target from functioning properly due to memory exhaustion.
Accordingly, it would be highly desirable to provide a method of defending against a denial-of-service attack targeting an IPv6 Neighbor Cache.